#!/usr/bin/python3

import math
import os
import re

epsilon = 0.0000001

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    
    def length(self):
        return math.sqrt(self.x * self.x + self.y * self.y)
    
def closest_pair(points):
    if len(points) == 1:
        return sys.maxsize
    if len(points) == 2:
        return (points[0] - points[1]).length()
    
    l = int(len(points)/2) 
    d = min(closest_pair(points[:l]), closest_pair(points[l:]))
        
    new_points = [point for point in points if not point.x - points[l].x > d]
    new_points.sort(key=lambda p: p.y)
    
    for i in range(len(new_points) - 1):
        for j in range(i+1, min(i+12, len(new_points))):
            d_c = (new_points[i] - new_points[j]).length()
            if d_c < d:
                d = d_c
    return d

def parse(filename):
    # taken from the assignment sheet 
    number = "[-+]?\d*\.?\d+(?:[eE][-+]?\d+)?"
    pattern = re.compile("(.+|\d+)\s+(%s)\s+(%s)" %(number, number))
    
    points = []
    with open(filename, "r") as f:
        for line in f:
            match = re.search(pattern, line)
            if match:
                points.append(Point(x=float(match.group(2)),
                                    y=float(match.group(3))))
    return points

def nearly_equal(a, b):
    
    abs_a = math.fabs(a)
    abs_b = math.fabs(b)
    diff = math.fabs(a - b)
    
    if a == b:
        return True
    elif a * b == 0:
        return diff < (epsilon * epsilon)
    else:
        return diff / (abs_a + abs_b) < epsilon
        
def check_result(filename, card, result):
    name = os.path.basename(filename).replace(".", "\.")
    pattern = re.compile(".+%s\:\s(\d+)\s(\d*\.?\d+)" %name)
    with open(os.path.join(os.path.dirname(os.path.abspath(__file__)),
                           "testfiles",
                           "closest-pair.out"), "r") as f:
        for line in f:
            match = re.search(pattern, line)
            if match:
                assert int(match.group(1)) == card, "%s != %d" %(match.group(1), card)
                assert nearly_equal(float(match.group(2)), float(result)), "%.15f != %.15f" %(float(match.group(2)), result)
                return

if __name__ == "__main__":
    import sys
    
    for arg in sys.argv[1:]:
        points = parse(arg)
        
        # sort points _before_ running algorithm
        points.sort(key=lambda p: p.x)
        d = closest_pair(points)
        
        check_result(arg, len(points), d)
        print(d)
